#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
using namespace std;

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_map<string, int> hash;
    for (auto x : wordDict) hash[x]++;

    int n = s.size();
    vector<bool> dp(n + 1);
    dp[0] = true;
    s = ' ' + s;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j >= 1; j--)
        {
            if (dp[j - 1] && hash[s.substr(j, i - j + 1)])
            {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}

int findSubstringInWraproundString(string s) {
    int n = s.size();
    vector<int> dp(n, 1);
    int arr[26] = { 0 };
    arr[s[0] - 'a'] = 1;
    for (int i = 1; i < n; i++)
    {
        if (s[i - 1] + 1 == s[i] || (s[i - 1] == 'z' && s[i] == 'a'))
            dp[i] += dp[i - 1];
        if (dp[i] > arr[s[i] - 'a']) arr[s[i] - 'a'] = dp[i];
    }
    int ret = 0;
    for (auto x : arr) ret += x;
    return ret;
}
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    for (int i = 1; i < n; i++)
    {
        for (int j = i - 1; j >= 0; j--)
        {
            if (nums[i] > nums[j])
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    int ret = 1;
    for (auto x : dp)
        if (x > ret) ret = x;
    return ret;
}

int wiggleMaxLength(vector<int>& nums) {
    if (nums.size() == 1)
        return 1;
    int i = 1;
    int ret = 1;
    for (i = 1; i < nums.size() - 1; i++)
    {
        if ((nums[i] < nums[i - 1] && nums[i] < nums[i + 1]) || (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]))
        {
            ret++;
        }
        if (nums[i] == nums[i + 1])
        {
            int j = i + 1;
            while (1)
            {
                nums.erase(nums.begin() + j);
                if (i == nums.size() - 1 || nums[i] != nums[i + 1])
                    break;
            }
            if (((i == nums.size() - 1) || ((nums[i] < nums[i - 1] && nums[i] < nums[i + 1]) || (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]))) && (nums[i] != nums[i - 1]))
            {
                ret++;
            }
        }
    }
    if (nums[i] == nums[i - 1]) return ret;
    if (i == nums.size() - 1) ret++;
    return ret;
}

int main()
{
    vector<string> v{ "apple", "pen" };
    wordBreak("applepenapple", v);
    findSubstringInWraproundString("cac");
    cout << 'a' + 1;
    vector<int> a{ 1,17,5,10,11,15,10,5,16,8 };
    wiggleMaxLength(a);
    lengthOfLIS(a);
	return 0;
}